package com.ronz.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
import java.util.Random;

/**
 * @Description 希尔排序
 * @Author Ronz
 * @Date 2021/1/10 11:57
 * @Version 1.0
 */
public class No4_ShellSort {

    public static void main(String[] args) {
        int[] arr = {8,9,1,7,2,3,5,4,6,0};

        System.out.println("原始序列為：" + Arrays.toString(arr));
        shellSort(arr);
        System.out.println("最終序列為：" + Arrays.toString(arr));


    }



    public static void shellSort(int[] arr){

        int gap = arr.length/2;
        int count = 1;
        while(gap > 0) {

            /* 数据被分成 gap 组，所以要循环 gap 次 */
            for(int i=0; i<gap; i++){
                /* N 个元素要进行 N-1 次插入排序。数据被分成 gap 组，则每组有 arr.length/gap 个元素 */
                for(int j=1; j<arr.length/gap; j++){
                    int index = i+gap*j;			// 初始索引，以增量 gap 递增，细品
                    int indexVal = arr[i+gap*j];	// 初始索引指向的值
                    while(index-gap>=0 && arr[index-gap]>indexVal){
                        /* 比索引指向的值大，就右移腾出空间 */
                        arr[index] = arr[index-gap];
                        index -= gap;
                    }
                    if(index != i+gap*j){
                        arr[index] = indexVal;
                    }
                }
            }
            gap /= 2;
            System.out.println("第 " + count++ + " 輪排序後：" + Arrays.toString(arr));
        }

    }

}
